顾森 | 中国剩余定理与贝祖定理
编者按：本号曾推文《顾森新书《神机妙算：一本关于算法的闲书》 | 图论算法：稳定婚姻问题》推荐顾森的新书。经编辑推荐，我们再转发一篇该书中的文章。
如果您有兴趣获赠该书，可以到《顾森新书《神机妙算：一本关于算法的闲书》 | 图论算法：稳定婚姻问题》后面留言。获赞最高的5为读者将有机会获得出版社的赠书。12月9日晚12时截止。
如果两个正整数的最大公约数为 1，我们就说这两个数是互质的（relatively prime，也叫作互素的）。这是一个非常重要的概念。如果 𝑎 和 𝑏 互质，就意味着分数 𝑎/𝑏 已经不能再约分了，意味着 𝑎 × 𝑏 的棋盘的对角线不会经过中间的任何交叉点（如图 1 所示），意味着循环长度分别为 𝑎 和 𝑏 的两个周期性事件一同上演，则新的循环长度最短为 𝑎 · 𝑏。
图 1 正方形网格中的两个矩形，后者的对角线经过了中间的一个交叉点
最后一点可能需要一些解释。让我们来举些例子。
假如有 1 路和 2 路两种公交车，其中 1 路车每 6 分钟一班，2 路车每 8 分钟一班。如果你刚刚错过两路公交车同时出发的壮景，那么下一次再遇到这样的事情是多少分钟之后呢？当然，6 × 8 = 48 分钟，这是一个正确的答案，此时 1 路公交车正好是第 8 班，2 路公交车正好是第 6 班。不过，实际上，在第 24 分钟就已经出现了两车再次同发的情况了，此时 1 路车正好是第 4 班，2 路车正好是第 3 班。但是，如果把例子中的 6 分钟和 8 分钟分别改成 4 分钟和 7 分钟，那么要想等到两车再次同发，等到第 4 × 7 = 28 分钟是必需的。与之类似，假如某一首歌的长度正好是 6 分钟，另一首歌的长度正好是 8 分钟，让两首歌各自循环播放，6 × 8 = 48 分钟之后你听到的“合声”将会重复，但实际上第 24 分钟就已经开始重复了。但若两首歌的长度分别是 4 分钟和 7 分钟，则必须到第 4 × 7 = 28 分钟之后才有重复，循环现象不会提前发生。
究其原因，其实就是，对于任意两个数，两个数的乘积一定是它们的一个公倍数，但若这两个数互质，则它们的乘积一定是它们的最小公倍数。事实上，我们还能证明一个更强的结论：𝑎 和 𝑏 的最大公约数和最小公倍数的乘积，一定等于 𝑎 和 𝑏 的乘积。在下一篇文章中，我们会给出一个证明。
很多更复杂的数学现象也都跟互质有关。
《孙子算经》卷下第二十六问：“今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？答曰：二十三。”翻译过来，就是有一堆东西，三个三个数余 2，五个五个数余 3，七个七个数余 2，问这堆东西有多少个？《孙子算经》给出的答案是 23 个。当然，这个问题还有很多其他的解。
由于105 = 3 × 5 × 7，因而 105 这个数被 3 除、被 5 除、被 7 除都能除尽。这表明，将物体的个数增加 105 以后，不管是三个三个数，还是五个五个数，还是七个七个数，所得的余数都会不变。因此，在 23 的基础上额外加上一个105，得到的 128 也是满足要求的解。当然，我们还可以在 23 的基础上加上2 个 105，加上 3 个 105，等等，所得的数都满足要求。
除了形如 23 + 105𝑛的数以外，还有别的解吗？没有了。事实上，不管物体总数除以 3 的余数、除以 5 的余数及除以 7 的余数分别是多少，在 0 到 104 当中总存在唯一解；在这个解的基础上再加上 105 的整数倍后，可以得到其他所有的正整数解。后人将其表述为“中国剩余定理”（Chinese remainder theorem）：给出 𝑚 个两两互质的整数，它们的乘积为 𝑃；假设有一个未知数 𝑀，如果我们已知𝑀 分别除以这 𝑚 个数所得的余数，那么在 0 到 𝑃 −1 的范围内，我们可以唯一地确定这个 𝑀。这可以看作是 𝑀 的一个特解。其他所有满足要求的 𝑀，则正好是那些除以 𝑃 之后余数等于这个特解的数。注意，除数互质的条件是必需的，否则结论就不成立了。比如说，在 0 到 7 的范围内，除以 4 余 1 并且除以 2 也余 1 的数有 2 个，除以 4 余 1 并且除以 2 余 0 的数则一个也没有。
从某种角度来说，中国剩余定理几乎是显然的。让我们以两个除数的情况为例，来说明中国剩余定理背后的直觉吧。假设两个除数分别是 4 和 7。下表显示的就是各自然数除以 4 和除以 7 的余数情况，其中 𝑥 mod 𝑦 表示 𝑥 除以 𝑦 的余数，这个记号后面还会用到。
𝑖 mod 4 的值显然是以 4 为周期在循环，𝑖 mod 7 的值显然是以 7 为周期在循环。由于 4 和 7 是互质的，它们的最小公倍数是 4 × 7 = 28，因而(𝑖 mod 4, 𝑖 mod 7) 的循环周期是 28，不会更短。因此，当 𝑖 从 0 增加到 27时，(𝑖 mod 4, 𝑖 mod 7) 的值始终没有出现重复。但是，(𝑖 mod 4, 𝑖 mod 7) 也就只有 4 × 7 = 28 种不同的取值，因而它们正好既无重复又无遗漏地分给了 0 到 27 之间的数。这说明，每个特定的余数组合都在前 28 项中出现过，并且都只出现过一次。在此之后，余数组合将产生长度为 28 的循环，于是每个特定的余数组合都将会以 28 为周期重复出现。这正是中国剩余定理的内容。
中国剩余定理是一个很基本的定理。很多数学现象都可以用中国剩余定理来解释。背九九乘法口诀表时，你或许会发现，写下 3×1, 3×2, ⋯ , 3×9，它们的个位数正好遍历了 1 到 9 所有的情况。7 的倍数、9 的倍数也是如此，但 2、4、5、6、8 就不行。3、7、9 这三个数究竟有什么特别的地方呢？秘密就在于，3、7、9 都是和 10 互质的。比如说 3，由于 3 和 10 是互质的，那么根据中国剩余定理，在 0 到 29 之间一定有这样一个数，它除以 3 余 0，并且除以 10 余 1。它将会是 3 的某个整倍数，并且个位为 1。同样，在 0 到29 之间也一定有一个 3 的整倍数，它的个位是 2；在 0 到 29 之间也一定有一个 3 的整倍数，它的个位是 3……而在 0 到 29 之间，除掉 0 以外，3 的整倍数正好有 9 个，于是它们的末位就正好既无重复又无遗漏地取遍了 1 到 9 所有的数字。
这表明，如果 𝑎 和 𝑛 互质，那么 (𝑎·𝑥) mod 𝑛 = 1、(𝑎·𝑥) mod 𝑛 = 2 等所有关于 𝑥 的方程都是有解的。18 世纪的法国数学家艾蒂安·贝祖（ÉtienneBézout）曾经证明了一个基本上与此等价的定理，这里我们姑且把它叫作“贝祖定理”（Bézout’s theorem）。事实上，我们不但知道上述方程是有解的，还能求出所有满足要求的解来。
我们不妨花点时间，把方程 (𝑎 · 𝑥) mod 𝑛 = 𝑏 和中国剩余定理的关系再理一下。寻找方程 (𝑎 · 𝑥) mod 𝑛 = 𝑏 的解，相当于寻找一个 𝑎 的倍数使得它除以 𝑛 余 𝑏，或者说是寻找一个数 𝑀 同时满足 𝑀 mod 𝑎 = 0 且 𝑀 mod 𝑛 = 𝑏。如果 𝑎 和 𝑛 是互质的，那么根据中国剩余定理，这样的 𝑀一定存在，并且找到一个这样的 𝑀 之后，在它的基础上加减 𝑎 · 𝑛 的整倍数，可以得到所有满足要求的 𝑀。因此，为了解出方程 (𝑎 · 𝑥) mod 𝑛 = 𝑏的所有解，我们也只需要解出方程的某个特解就行了。假如我们找到了方程 (𝑎 · 𝑥) mod 𝑛 = 𝑏 中 𝑥 的一个解，在这个解的基础上加上或减去 𝑛 的倍数（相当于在整个被除数 𝑀 = 𝑎 · 𝑥 的基础上加上或者减去 𝑎 · 𝑛 的倍数），就能得到所有的解了。
更妙的是，我们其实只需要考虑形如 (𝑎 · 𝑥) mod 𝑛 = 1 的方程。因为，如果能解出这样的方程，(𝑎 · 𝑥) mod 𝑛 = 2、(𝑎 · 𝑥) mod 𝑛 = 3 也都自动地获解了。假如 (𝑎 · 𝑥) mod 𝑛 = 1 有一个解 𝑥 = 100，由于 100 个 𝑎 除以 𝑛 余 1，自然 200 个 𝑎 除以 𝑛 就余 2，300 个 𝑎 除以 𝑛 就余 3，等等，等式右边余数不为 1 的方程也都解开了。
让我们尝试求解 (115𝑥) mod 367 = 1。注意，由于 115 和 367 是互质的，因此方程确实有解。我们解方程的基本思路是，不断寻找 115 的某个倍数及 367 的某个倍数，使得它们之间的差越来越小，直到最终变为 1。由于 367 除以 115 得 3，余 22，因而 3 个 115 只比 367 少 22。于是，15 个 115就要比 5 个 367 少 110，从而 16 个 115 就会比 5 个 367 多 5。
好了，真正巧妙的就在这里：16 个 115 比 5 个 367 多 5，但 3 个 115 比 1 个 367 少 22，两者结合起来，我们便能找到 115 的某个倍数和 367 的某个倍数，它们只相差 2：16 个 115 比 5 个 367 多 5，说明 64 个 115 比 20 个 367 多 20，又考虑到 3 个 115 比 1 个 367 少 22，于是 67 个 115 只比 21 个 367 少 2。
现在，结合“少 2”和“多 5”两个式子，我们就能把差距缩小到 1 了：67 个 115比 21 个 367 少 2，说明 134 个 115 比 42 个 367 少 4，而 16 个 115 比 5 个367 多 5，于是 150 个 115 比 47 个 367 多 1。这样，我们就解出了一个满足(115𝑥) mod 367 = 1 的 𝑥，即 𝑥 = 150。
大家会发现，在求解过程中，我们相当于对 115 和 367 做了一遍辗转相除：我们不断给出 115 的某个倍数和367 的某个倍数，通过辗转对比最近的两个结果，让它们的差距从“少 22”缩小到“多 5”，再到“少 2”、“多 1”，其中 22, 5, 2, 1 这几个数正是用辗转相除法求 115 和 367 的最大公约数时将会经历的数。因而，算法的步骤数仍然是对数级的，即使面对上百位上千位的大数，计算机也毫无压力。这种求解方程 (𝑎 · 𝑥) mod 𝑛 = 𝑏 的算法就叫作“扩展的辗转相除法”。
注意，整个算法有时也会以“少 1”的形式告终。例如，用此方法求解(128𝑥) mod 367 = 1 时，最后会得出 43 个 128 比 15 个 367 少 1。这下怎么办呢？很简单，43 个 128 比 15 个 367 少 1，但是 367 个 128 显然等于 128 个367，对比两个式子可知，324 个 128 就会比 113 个 367 多 1 了，于是得到𝑥 = 324。
我们最终总能到达“多 1”或者“少 1”，这正是因为一开始的两个数是互质的。如果方程 (𝑎 · 𝑥) mod 𝑛 = 𝑏 当中 𝑎 和 𝑛 不互质，它们的最大公约数是 𝑑 > 1，那么在 𝑎 和 𝑛 之间做辗转相除时，算到 𝑑 就直接终止了。自然，扩展的辗转相除也将在到达“多 1”或者“少 1”之前提前结束。那么，这样的方程我们还能解吗？能！我们有一种巧妙的处理方法：以 𝑑 为单位重新去度量 𝑎 和 𝑛（或者说让 𝑎 和 𝑛 都除以 𝑑），问题就变成我们熟悉的情况了。
* 本文摘自《神机妙算：一本关于算法的闲书》一书，欢迎阅读此书了解更多有关数学和算法的内容！
▊《神机妙算：一本关于算法的闲书》
顾森 著，蔡雪琴 绘
购买链接如下：
END精选推荐
01 | |
02 | |
03 |
■ END ■
线性代数第六版答案：第一章习题解答 | 第二章习题解答 | 第三章习题解答 | 第四章习题解答 | 第五章习题解答 | 第六章习题解答 | 《线性代数》同济版 第六版 各章知识框架全解
让我知道你在看